package com.justnow.offer;

public class Solution08 {

    public TreeLinkNode getNext(TreeLinkNode pNode) {

        //情况一：pNode节点存在右子树，那么其下一个节点是pNode左子树的最左节点
        if(pNode == null)
            return null;
        TreeLinkNode pNext = null;
        if (pNode.right != null) {
            TreeLinkNode pRight = pNode.right;
            while (pRight.left != null) {
                pRight = pRight.left;
            }
            pNext = pRight;
        } else if (pNode.next != null) {
            /**
             * 情况二，pNode节点不存在右子树，那么共分为两种情况的内容
             * 第一，pNode节点为它父节点的左子节点，那么下一个节点就是其父节点
             * 第二，pNode节点为它父节点的右子节点，那么可以沿着指向父节点的指针一直向上
             * 遍历，直到找到一个是它父节点的左子节点的节点。如果这个节点存在，那么这个节点的
             * 父节点就是我们要找的下一个节点
             */
            TreeLinkNode pCurrent = pNode;
            TreeLinkNode pParent = pNode.next;
            while (pParent != null && pCurrent == pParent.right) {
                pCurrent = pParent;
                pParent = pParent.next;
            }

            pNext = pParent;


        }
        return pNext;
    }
}

class TreeLinkNode {

    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode (int val) {
        this.val = val;
    }

}